package com.cuz.hot100;

public class Q79WordsSearch {
    public static void main(String[] args) {
        char[][] chars = {
                new char[]{'A', 'B', 'C', 'E'},
                new char[]{'S', 'F', 'E', 'S'},
                new char[]{'A', 'D', 'E', 'E'}
        };
        //[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
        //"ABCESEEEFS"
        System.out.println(exist1(chars, "ABCESEEEFS"));
    }


    public static boolean exist1(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return word == null || word.length() == 0;
        }
        if (word == null || word.length() == 0) {
            return true;
        }
        char[] chars = word.toCharArray();
        char firstChar = chars[0];
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (board[row][col] == firstChar) {
                    boolean[][] visited = new boolean[board.length][board[0].length];
                    boolean flag1 = process(row, col, 0, board, visited, word);
                    if (flag1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private static boolean process(int x, int y, int curFindCharIndex, char[][] board, boolean[][] visited, String word) {
        if (x < 0 || x >= board.length) {
            return false;
        }
        if (y < 0 || y >= board[0].length) {
            return false;
        }
        if (visited[x][y]) {
            return false;
        }
        if (board[x][y] != word.charAt(curFindCharIndex)) {
            return false;
        }
        if (curFindCharIndex == word.length() - 1) {
            return true;
        }
        visited[x][y] = true;
        boolean b = process(x + 1, y, curFindCharIndex + 1, board, visited, word)
                || process(x - 1, y, curFindCharIndex + 1, board, visited, word)
                || process(x, y + 1, curFindCharIndex + 1, board, visited, word)
                || process(x, y - 1, curFindCharIndex + 1, board, visited, word);
        visited[x][y] = false;
        return b;
    }

}
